#include<stdio.h>
#include<stdlib.h>
#include<string.h>

// using python for pseudo code
/*
    def letterCombinations(self, digits: str) -> List[str]:
        numl = [int(i) for i in digits]
        if len(numl)==0:
            return []
        numd = ["abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
        res = [""]
        for i in numl:
            N = len(res)
            for _ in range(N):
                tmp = res.pop(0)
                for k in range(len(numd[i-2])):
                    res.append(tmp+numd[i-2][k])
        return res
*/

char** letterCombinations(char* digits, int* returnSize)
{
    int N = strlen(digits);
    char* table[10] = {0,0,"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    // final res size at most 4^N = 2^(2N)
    // implement as a circular deque
    const int NUM = 1<<2*N;
    char** res = (char**)malloc(sizeof(char*) * NUM);
    // but note you need to return the ans start from 0, need to copy queue to tres
    char** tres = (char**)malloc(sizeof(char*) * NUM);
    int front = 0, back=0; *returnSize = 0;
    if(N)
    {
        res[back] = (char*)malloc(sizeof(char)*5); res[back][0] = 0; back++;
        for(int i = 0; i<N;++i)
        {
            int dig = digits[i]-'0';
            int csize = (back-front)%NUM;
            for(int _=0;_<csize;++_)
            {
                char* tmp = res[front++];front%=NUM;
                for(int k = 0;table[dig][k];++k)
                {
                    char* stmp = (char*)malloc(sizeof(char)*5);
                    // stmp = tmp+table[dig][k]
                    strcpy(stmp,tmp); int tmpl = strlen(stmp); stmp[tmpl] = table[dig][k]; stmp[tmpl+1] = 0;
                    // res.append(stmp)
                    res[back++] = stmp; back%=NUM;
                }
            }
        }
        *returnSize = (back-front)%NUM;
    }
    for(int i = 0;i<*returnSize;++i) tres[i] = res[(front+i)%NUM];
    free(res);
    return res;
}


int main(int argc, char const *argv[])
{
    freopen("./medium/test.txt","r",stdin);
    const int NUM = 10;
    char digits[NUM]; scanf("%s",digits);
    int returnSize;

    letterCombinations(digits,&returnSize);

    return 0;
}
